package com.algorithm.串匹配;

public class KMP {

    public static int indexOf2(String text, String pattern) {
        if (text == null || pattern == null) return -1;

        char[] textChars = text.toCharArray();
        int tlen = textChars.length;
        if (tlen == 0) return -1;
        char[] patternChars = pattern.toCharArray();
        int plen = patternChars.length;
        if (plen == 0) return -1;

        if (plen > tlen) return -1;

        int[] next = next(pattern);

        int pi = 0, ti = 0;
        // ti - pi: (文本串正在匹配的子串的开始索引)
        // tlen - plen: (开始索引的临界值)
        // tlen - plen为临界值，保证ti - pi始终小于这个临界值，那么说明tlen未比较的长度大于plen
        // ti - pi <= tlen - plen
        int lenDelte = tlen - plen;
        while (pi < plen && ti - pi <= lenDelte) {
            if (pi < 0 || textChars[ti] == patternChars[pi]) {
                pi++;
                ti++;
            } else {
                pi = next[pi];
            }
        }
        return (pi == plen) ? (ti - pi) : -1;
    }

    private static int[] next(String pattern) {
        //TODO: next数组的实现
        return null;
    }
}
